package main

import (
	"container/list"
	"fmt"
	"log"
	"math"
	"sort"
	"strconv"
	"strings"
	"unicode"
)

type arrT interface {
	~int | ~string
}

// mergeTowSortedArr 合并两个有序数组
func mergeTowSortedArr[T arrT](s1, s2 []T) []T {
	var res []T
	for len(s1) != 0 && len(s2) != 0 {
		if s1[0] <= s2[0] {
			res = append(res, s1[0])
			s1 = s1[1:]
		} else {
			res = append(res, s2[0])
			s2 = s2[1:]
		}
	}
	if len(s1) != 0 {
		res = append(res, s1...)
	}
	if len(s2) != 0 {
		res = append(res, s2...)
	}
	return res
}

// merge 合并两个有序数组
func merge(nums1 []int, m int, nums2 []int, n int) {
	var (
		numsOne []int
		numsTow []int
	)
	numsOne = append(numsOne, nums1...)
	numsTow = append(numsTow, nums2...)
	var res []int
	log.Printf("%p,%p", nums1, numsOne)
	for m > 0 && n > 0 {
		if numsOne[0] <= numsTow[0] {
			res = append(res, numsOne[0])
			numsOne = numsOne[1:]
			m--
		} else {
			res = append(res, numsTow[0])
			numsTow = numsTow[1:]
			n--
		}
	}
	if m == 0 {
		res = append(res, numsTow...)
	} else {
		res = append(res, numsOne...)
	}
	nums1 = append(nums1, res...)
	for i, v := range res {
		nums1[i] = v
	}
}

type test[T arrT] struct {
	val T
}

// inPlaceDel 原地移除有序数组中的目标元素
func inPlaceDel[T arrT](s []T, target T) []T {
	var k int
	for i, v := range s {
		if target != v {
			s[k] = s[i]
			k++
		}
	}
	return s[:k]
}

// inPlaceDelCappedTower 删除有序数组中重复次数超过2的元素的超过部分
func inPlaceDelCappedTower[T arrT](s []T) []T {
	k := 2
	for _, v := range s[2:] {
		if v != s[k-2] {
			s[k] = v
			k++
		}
	}
	return s[:k]
}

// inPlaceStoreOneDel 删除有序数组中重复元素，使得重复元素只出现一次
func inPlaceStoreOneDel[T arrT](s []T) []T {
	k := 1
	for _, v := range s[1:] {
		if v != s[k-1] {
			s[k] = v
			k++
		}
	}
	return s[:k]
}

// majority 找到多数元素：如果有多数元素，多数元素出现次数一定比其他元素出现次数和多
func majorityElement[T arrT](s []T) T {
	var candidate T
	count := 0

	for _, v := range s {
		if count == 0 {
			candidate = v
		}
		if candidate == v {
			count++
		} else {
			count--
		}
	}
	appears := 0
	for _, v := range s {
		if candidate == v {
			appears++
		}
	}
	var res T
	if appears > len(s)/2 {
		res = candidate
	}
	return res
}

// rotate 把所有元素向右反转k个位置
func rotate[T arrT](nums []T, k int) []T {
	tmp := make([]T, len(nums))
	for i, v := range nums {
		tmp[(i+k)%len(nums)] = v
	}
	copy(nums, tmp)
	return nums
}

// maxProfit 股票最大汇报率
func maxProfit(s []float64) float64 {
	minPrice, profit := s[0], 0.0
	for _, v := range s[1:] {
		if minPrice < v {
			currentProfit := v - minPrice
			if currentProfit > profit {
				profit = currentProfit
			}
		} else {
			minPrice = v
		}
	}
	return profit
}

// maxReset 股票最大回撤率
func maxReset(s []float64) float64 {
	maxPrice, reset := s[0], 0.0
	for _, v := range s[1:] {
		if maxPrice < v {
			maxPrice = v
		} else {
			currentReset := v - maxPrice
			if currentReset < reset {
				reset = currentReset
			}
		}
	}
	return reset
}

// redAlgorithm 简单红包算法
func redAlgorithm() {
	a := 0.00
	b := 100.00
	n := 10
	for i := 0; i < n-1; i++ {
		red := float64(b/float64(n-i)) * 2
		//log.Print(red)
		a += red
		b -= red
	}
	log.Print(a, b)
}

// noRepeatChildStr 最长不重复子串
func noRepeatChildStr(s string) string {
	left := 0
	maxLen := 0
	lastOccurred := make(map[rune]int)
	start := 0
	for right, v := range []rune(s) {
		if lastI, ok := lastOccurred[v]; ok && lastI >= left {
			left = lastI + 1
		}
		if right-left+1 > maxLen {
			maxLen = right - left + 1
			start = left
		}
		lastOccurred[v] = right
	}
	return string([]rune(s)[start : start+maxLen])
}

// cycleStreet 加油站问题-有意思的解法
func cycleStreet(gas, cost []int) int {
	a, b, c := 0, 0, 0
	for i := 0; i < len(gas); i++ {
		a += gas[i] - cost[i]
		if a < b {
			b = a
			c = i + 1
		}
	}
	if a >= 0 {
		return c
	}
	return -1
}

// receiveWater 接雨水
func receiveWater(waters []int) int {
	c := len(waters)
	leftMax, rightMax := make([]int, c), make([]int, c)
	leftMax[0] = waters[0]
	for i := 1; i < c; i++ {
		leftMax[i] = int(math.Max(float64(waters[i]), float64(leftMax[i-1])))
	}
	rightMax[c-1] = waters[c-1]
	for j := c - 2; j >= 0; j-- {
		rightMax[j] = int(math.Max(float64(waters[j]), float64(rightMax[j+1])))
	}
	num := 0
	for i := 0; i < c; i++ {
		num += int(math.Min(float64(leftMax[i]), float64(rightMax[i])) - float64(waters[i]))
	}
	return num
}

// maxProfitTow 买卖股票的最大回报2
func maxProfitTow(prices []int) int {
	profit := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			profit += prices[i] - prices[i-1]
		}
	}
	return profit
}

// skipGame 跳跃游戏
func skipGame(nums []int) bool {
	maxPosition := 0
	for i := 0; i < len(nums); i++ {
		if i > maxPosition {
			return false
		}
		maxPosition = getMax(maxPosition, i+nums[i])
		if maxPosition >= len(nums)-1 {
			return true
		}
	}
	return false
}

// skipGameTwo 跳跃游戏2  32104
func skipGameTwo(nums []int) int {
	maxPosition, jumps, currentPosition := 0, 0, 0
	for i := 0; i < len(nums); i++ {
		maxPosition = getMax(maxPosition, i+nums[i])
		if i == currentPosition {
			jumps++
			currentPosition = maxPosition
			if currentPosition >= len(nums)-1 {
				return jumps
			}
		}
	}
	return -1
}

// jump 跳跃游戏2 好简单的解法
func jump(nums []int) int {
	cur := 0
	nxt := 0
	ans := 0
	for i, v := range nums[:len(nums)-1] {
		nxt = getMax(nxt, i+v)
		if i == cur {
			cur = nxt
			ans++
		}
	}
	return ans
}

func getMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// productExceptSelf 除自身外数组的乘积
func productExceptSelf(nums []int) []int {
	res := make([]int, len(nums))
	res[0] = 1
	for i := 1; i < len(nums); i++ {
		res[i] = res[i-1] * nums[i-1]
	}
	right := 1
	for i := len(nums) - 1; i >= 0; i-- {
		res[i] = res[i] * right
		right *= nums[i]
	}
	return res
}

// lruT lru算法：淘汰最近最少使用
type lruT interface {
	~int | ~string
}

type lruCache[T lruT] struct {
	capacity int
	cache    map[T]*list.Element
	list     *list.List
}

type lruType[T lruT] struct {
	key T
	val T
}

func (lru *lruCache[T]) get(key T) T {
	var t T
	if element, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(element)
		t = element.Value.(lruType[T]).val
	}
	return t
}

func (lru *lruCache[T]) set(key T, val T) {
	if element, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(element)
		return
	}
	if lru.list.Len() == lru.capacity {
		lru.moveOldElement()
	}
	lru.cache[key] = lru.list.PushFront(lruType[T]{key, val})
}

func (lru *lruCache[T]) moveOldElement() {
	element := lru.list.Back()
	if element != nil {
		delete(lru.cache, element.Value.(lruType[T]).key)
		lru.list.Remove(element)
	}
}

// h指数
func h() int {
	s := []int{6, 5, 4, 3, 2, 1}
	sort.Sort(sort.Reverse(sort.IntSlice(s)))
	for i, v := range s {
		if i+1 > v {
			return i
		}
	}
	return len(s)
}

// isPalindrome1 验证回文字符串
func isPalindrome1() {
	s := "A man, a plan, a canal: Panama"
	s = strings.ToLower(s)
	var r []rune
	for _, v := range s {
		if unicode.IsDigit(v) || unicode.IsLetter(v) {
			r = append(r, v)
		}
	}
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		if r[i] != r[j] {
			log.Print(false)
		}
	}
}

// maxK 返回数组topK个元素
func maxK(s []int, k int) []int {
	if k > len(s) {
		k = len(s)
	}
	res := make([]int, 0, k)
	for _, v := range s {
		res = append(res, v)
		for i := len(res) - 1; i > 0 && res[i] > res[i-1]; i-- {
			res[i], res[i-1] = res[i-1], res[i]
		}
		if len(res) > k {
			res = res[:k]
		}
	}
	return res
}

// romanToInt 罗马数字转整数
func romanToInt(s string) int {
	var (
		romanIntMap = map[rune]int{
			'I': 1,
			'V': 5,
			'X': 10,
			'L': 50,
			'C': 100,
			'D': 500,
			'M': 1000,
		}
		res int
	)
	for i, v := range s {
		current := romanIntMap[v]
		if i < len(s)-1 && current < romanIntMap[rune(s[i+1])] {
			res -= current
		} else {
			res += current
		}
	}
	return res
}

type interval struct {
	start int
	end   int
}

// sliceToInterval 把一维slice转换成[]interval
func sliceToInterval(s []int) (res []interval) {
	res = make([]interval, 0, len(s)/2)
	for i := 0; i < len(s); i += 2 {
		res = append(res, interval{start: s[i], end: s[i+1]})
	}
	return
}

// mergeInterval 合并两个升序的区间，并去掉重复元素
func mergeInterval(intervals []interval, newIntervals []interval) []interval {
	intervalAll := append(intervals, newIntervals...)
	// 先按开始元素升序排序，相等时，按结束元素升序排序
	sort.Slice(intervalAll, func(i, j int) bool {
		if intervalAll[i].start == intervalAll[j].start {
			return intervalAll[i].end < intervalAll[j].end
		}
		return intervalAll[i].start < intervalAll[j].start
	})
	// 合并重叠区间：前一个区间的结束值大于后一个区间开始值，更新前一区间结束值=max(前一区间结束值,后一区间结束值)
	merged := make([]interval, 0, len(intervals)+len(newIntervals))
	for _, val := range intervalAll {
		if len(merged) == 0 || merged[len(merged)-1].end < val.start {
			merged = append(merged, val)
		} else {
			merged[len(merged)-1].end = getMax(merged[len(merged)-1].end, val.end)
		}
	}
	return merged
}

// intToRoman 整数转罗马数字
func intToRoman(num int) string {
	// 定义所有可能的罗马数字符号及其对应的整数值
	values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}

	var result string

	// 遍历所有符号，尽可能地减去相应的值
	for i := 0; i < len(values); i++ {
		// 使用当前符号表示的值来更新结果字符串
		for num >= values[i] {
			result += symbols[i]
			num -= values[i]
		}
	}

	return result
}

// lengthOfLastWord 字符串最后一个单词的长度
func lengthOfLastWord(s string) int {
	s += " "
	var currentLen, lastLen int
	for _, v := range s {
		if v != ' ' {
			currentLen++
		} else {
			if currentLen != 0 {
				lastLen = currentLen
			}
			currentLen = 0
		}
	}
	return lastLen
}

// longestCommonPrefix 寻找字符串数组的最长公共前缀
func longestCommonPrefix(s []string) string {
	if len(s) <= 0 {
		return ""
	}
	prefix := s[0]
	for _, str := range s[1:] {
		for len(str) < len(prefix) || str[:len(prefix)] != prefix {
			prefix = prefix[:len(prefix)-1]
			if prefix == "" {
				return ""
			}
		}
	}
	return prefix
}

// summary 汇总区间
func summary(nums []int) []string {
	var res []string
	if len(nums) == 0 {
		return res
	}
	start := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i-1]+1 != nums[i] {
			if start == nums[i-1] {
				res = append(res, strconv.Itoa(start))
			} else {
				res = append(res, fmt.Sprintf("%d->%d", start, nums[i-1]))
			}
			start = nums[i]
		}
	}
	if start == nums[len(nums)-1] {
		res = append(res, strconv.Itoa(start))
	} else {
		res = append(res, fmt.Sprintf("%d->%d", start, nums[len(nums)-1]))
	}
	return res
}

// convert 字符串Z字转换
func convert(s string, numRows int) string {
	// 如果行数为 1 或字符串长度小于行数，直接返回原字符串
	if numRows <= 1 || len(s) <= numRows {
		return s
	}

	// 创建一个长度为 numRows 的字符串数组来存储每一行
	rows := make([]string, numRows)

	// 初始化行号和方向标记（是否向下填充）
	currentRow := 0
	goingDown := false

	// 遍历字符串中的每个字符
	for _, char := range s {
		// 将当前字符加入到相应的行
		rows[currentRow] += string(char)

		// 判断是否需要改变方向
		if currentRow == 0 || currentRow == numRows-1 {
			goingDown = !goingDown
		}

		// 根据方向调整行号
		if goingDown {
			currentRow++
		} else {
			currentRow--
		}
	}

	// 拼接所有行并返回
	result := ""
	for _, row := range rows {
		result += row
	}
	return result
}

// minSubArray 最小和的子数组
func minSubArray(nums []int, target int) int {
	left, currentSum, minLen := 0, 0, len(nums)+1
	for right, v := range nums {
		currentSum += v
		for currentSum >= target {
			if minLen > right-left+1 {
				minLen = right - left + 1
			}
			currentSum -= nums[left]
			left++
		}
	}
	if minLen == len(nums)+1 {
		return 0
	}
	return minLen
}

// firstMatchIdx 找出字符串中第一个匹配项的下标
func firstMatchIdx(haystack, needle string) int {
	for i := 0; i < len(haystack)-len(needle); i++ {
		if haystack[i:i+len(needle)] == needle {
			return i
		}
	}
	return -1
}

// Function to compute the partial match (prefix) table
func computePrefix(needle string) []int {
	m := len(needle)
	prefix := make([]int, m)
	j := 0

	// 从第2个字符开始，计算每个位置的最长公共前后缀
	for i := 1; i < m; i++ {
		// 如果当前字符与前缀的字符匹配，增加前缀长度
		for j > 0 && needle[i] != needle[j] {
			j = prefix[j-1]
		}

		if needle[i] == needle[j] {
			j++
		}

		prefix[i] = j
	}

	return prefix
}

// Function to find the first occurrence of needle in haystack using KMP
// strStr 找出字符串中第一个匹配项的位置 KMP算法优化
func strStr(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}
	prefix := computePrefix(needle)
	n, m := len(haystack), len(needle)
	j := 0 // 指针指向needle的当前位置

	// 遍历haystack
	for i := 0; i < n; i++ {
		// 如果字符不匹配，使用prefix表跳过一些字符
		for j > 0 && haystack[i] != needle[j] {
			j = prefix[j-1]
		}

		// 如果字符匹配，j向前移动
		if haystack[i] == needle[j] {
			j++
		}

		// 如果整个needle匹配完成，返回匹配的位置
		if j == m {
			return i - m + 1
		}
	}

	return -1
}

// subSequence 是否是子序列
func subSequence(s, t string) bool {
	start := 0
	for _, vt := range t {
		if rune(s[start]) == vt {
			start++
		}
		if start == len(s) {
			return true
		}
	}
	return false
}

// isSubSequenceBatch 是否是子序列-索引表方法：适合大量待判断的子序列
func isSubSequenceBatch(subs []string, t string) map[string]bool {
	// 把t所有字符出现的位置放在索引表中
	idxTable := make(map[rune][]int, len(t))
	for i, v := range t {
		idxTable[v] = append(idxTable[v], i)
	}
	rest := make(map[string]bool, len(subs))
	// 逐个寻找subs是否为t的子序列
	for _, sub := range subs {
		isSub := true
		prev := -1
		for _, subV := range sub {
			positions, ok := idxTable[subV]
			if !ok {
				isSub = false
				break
			}
			// 二分查找比prev跟大的位置
			pos := binarySearch(positions, prev)
			if pos == -1 {
				isSub = false
				break
			}
			prev = positions[pos]
		}
		rest[sub] = isSub
	}
	return rest
}
func binarySearch(positions []int, prev int) int {
	left, right := 0, len(positions)-1
	for left <= right {
		mid := (right + left) / 2
		if positions[mid] > prev {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if left < len(positions) {
		return left
	}
	return -1
}

// 赎金信
func random(randsom, magazine string) bool {
	magazineMap := make(map[rune]int, len(magazine))
	randsomMap := make(map[rune]int, len(randsom))
	for _, v := range randsom {
		randsomMap[v]++
	}
	for _, v := range magazine {
		magazineMap[v]++
	}
	for i, v := range randsomMap {
		if v > magazineMap[i] {
			return false
		}
	}
	return true
}

// isIsomorphic 同构字符串
func isIsomorphic(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}

	sToT := make(map[byte]byte)
	tToS := make(map[byte]byte)

	for i := 0; i < len(s); i++ {
		if sToT[s[i]] != 0 && sToT[s[i]] != t[i] {
			return false
		}
		if tToS[t[i]] != 0 && tToS[t[i]] != s[i] {
			return false
		}

		sToT[s[i]] = t[i]
		tToS[t[i]] = s[i]
	}

	return true
}

// wordPattern 单词规律：和同构字符串一个实现思路
func wordPattern(pattern string, word string) bool {
	wordSlice := strings.Split(word, " ")
	if len(wordSlice) != len(pattern) {
		return false
	}
	pattermMap := make(map[string]string, len(pattern))
	wordMap := make(map[string]string, len(pattern))
	for i, p := range pattern {
		pStr := string(p)
		wordStr := wordSlice[i]
		if pattermMap[pStr] != "" && pattermMap[pStr] != wordStr {
			return false
		}
		if wordMap[wordStr] != "" && wordMap[wordStr] != pStr {
			return false
		}
		pattermMap[pStr] = wordStr
		wordMap[wordSlice[i]] = pStr
	}
	return true
}

// 寻找数组topK个element
func findArrTopK() {
	s := []int{1, 8, 10, 1, 2, 3, 4, 5, 5}
	k := 3
	res := make([]int, 0, k)
	for _, v := range s {
		res = append(res, v)
		for j := len(res) - 1; j > 0 && res[j] < res[j-1]; j-- {
			res[j], res[j-1] = res[j-1], res[j]
		}
		if len(res) > k {
			res = res[1:]
		}
	}
}

type tree struct {
	val   int
	left  *tree
	right *tree
}

// levelIteratorTree 二叉树最大深度
func levelIteratorTree(root *tree) int {
	if root == nil {
		return 0
	}

	queue := []*tree{root}
	depth := 0
	for len(queue) > 0 {
		for _, node := range queue {
			queue = queue[1:]
			if node.left != nil {
				queue = append(queue, node.left)
			}
			if node.right != nil {
				queue = append(queue, node.right)
			}
		}
		depth++
	}
	return depth
}

// searchInsert 搜索插入位置
func searchInsert(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}
	l, r := 0, len(nums)-1
	for l <= r {
		mid := l + (r-l)/2
		if nums[mid] > target {
			r = mid - 1
		} else if nums[mid] < target {
			l = mid + 1
		} else {
			return mid
		}
	}
	return l
}

// 两数之和
func twoSum(nums []int, target int) []int {
	if len(nums) < 2 {
		return []int{}
	}
	hash := make(map[int]int, len(nums))
	for i, num := range nums {
		complete := target - num
		if idx, ok := hash[complete]; ok {
			return []int{idx, i}
		}
		hash[num] = i
	}
	return []int{}
}
func main() {
	redAlgorithm()
}
